"""
已知一个能随机返回0或1的函数rand() ，请编写一个python函数，利用这个rand函数来随机生成 0～1000 之间的整数。
"""
import collections
import random
import re
from functools import reduce
from typing import List


def rand() -> int:
    digit = random.choice(0, 1)
    print(digit)
    return digit


def createInt():
    n = random(0, ((rand() + 1) * 1000))
    print(n)
w

"""
    斐波那契数列  F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）
"""


# 斐波那契数列 递推法，呈线性增长，时间复杂度是O(n)，如果数据量大的话 速度也会慢
def fib(n):
    a, b = 1, 1
    for i in range(n - 1):
        a, b = b, a + b
    # print(a)
    return a


# 斐波那契数列 使用递归(写法简洁，但是效率低，出现大量重复计算),时间复杂度O（1.618^n）,而且最大深度为1000
def fib1(n):
    if n == 1 or n == 2:
        return 1
    else:
        print(fib(n - 1) + fib(n - 2))
        return fib(n - 1) + fib(n - 2)


"""
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，请使用二分查找法编写一个python函数，搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
"""


def search():
    pass


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        """顺序查找"""
        for i, val in enumerate(nums):
            if val == target:
                return i
            elif val > target:
                return -1
        return -1

    def search1(self, nums: List[int], target: int) -> int:
        """二分查找"""
        left, right = 0, len(nums) - 1
        while left <= right:
            # mid = left + right >> 1
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        return -1

    def searchInsert(self, nums: List[int], target: int) -> int:
        """二分查找"""
        left, right = 0, len(nums)
        while left < right:
            mid = left + right >> 1
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

    # 字符串反转
    def dictzip(self):
        str = "微信公众号:ITester软件测试小栈"
        list_str = list(str.split(':'))
        list_str.reverse()
        print(":".join(list_str))

    # 水仙花数
    def fl(self):
        output = []
        for d in range(100, 1000):
            x = d // 100
            y = (d % 100) // 10
            z = d % 10
            s = x ** 3 + y ** 3 + z ** 3
            if s == d:
                output.append(d)
        print(output)

    def fl1(self):
        for i in range(100, 1000):
            sum = 0
            temp = i
            while temp:
                sum = sum + (temp % 10) ** 3
                temp //= 10
            if sum == i:
                print(i)

    def dictzip1(self):
        # zip(*zipped)  与 zip 相反，*zipped 可理解为解压，返回二维矩阵式

        str = '1234567890'
        print(str[::-1])
        l = list(str)
        l.reverse()
        print(''.join(l))

    def countt(self, n):
        if int(n) <= 1:
            return 1
        else:
            print(n * self.countt(n))
            return n * self.countt(n)

    """
    给定一个已按照 升序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
    """

    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        left, right = 0, len(numbers) - 1
        while left < right:
            if numbers[left] + numbers[right] < target:
                left = left + 1
            elif numbers[left] + numbers[right] > target:
                right = right - 1
            elif numbers[left] + numbers[right] == target:
                print(left, right)
                return left, right

    def db(num):
        # return re.sub(r'(\d+)', lambda x: str(int(x.group(1)) * 2), num)
        # a = '2018 Amazon Jeff Bezos 1120'
        # print(db(a))

        str1 = "rqerqw322341 dsfs 41 rwe"

        # p = lambda x: x*2
        # nums = re.split("\d",str1)
        # print(nums)
        # strnums = ''.join(nums)
        # print(strnums)
        # print(p(strnums))
        # b = re.sub("\d","哈",str1)
        # print(b)

        a = re.sub("\d", lambda x: str(int(x.group(1)) * 2), str1)
        print(a)

    def testt(self):
        a = lambda x: x * x
        print(a(3))

    """给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

        有效字符串需满足：
        
        左括号必须用相同类型的右括号闭合。
        左括号必须以正确的顺序闭合。


    """

    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        num = []
        for i in nums:
            if i in num:
                print(i)
                return i
            else:
                num.append(i)

    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False

        pairs = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        stack = list()
        for ch in s:
            if ch in pairs:
                if not stack or stack[-1] != pairs[ch]:
                    return False
                stack.pop()
            else:
                stack.append(ch)

        return not stack

    # 合并两个有序链表
    def mergeTwoLists(self, l1, l2):
        if not l1: return l2  # 终止条件，直到两个链表都空
        if not l2: return l1
        if l1.val <= l2.val:  # 递归调用
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

    """
    给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

    不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

    """

    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        n = len(nums)
        fast = slow = 1
        while fast < n:
            if nums[fast] != nums[fast - 1]:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

    # 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
    def removeElement(self, nums, val):
        needle = 0
        for i in nums:
            if i != val:
                nums[needle] = i
                needle += 1
        return needle

    # 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    def searchInsert1(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)  # 采用左闭右开区间[left,right)
        while left < right:  # 右开所以不能有=,区间不存在
            mid = left + (right - left) // 2  # 防止溢出, //表示整除
            if nums[mid] < target:  # 中点小于目标值,在右侧,可以得到相等位置
                left = mid + 1  # 左闭,所以要+1
            else:
                right = mid  # 右开,真正右端点为mid-1
        return left  # 此算法结束时保证left = right,返回谁都一样

    def searchInsert2(self, nums: List[int], target: int) -> int:
        """二分查找"""
        left, right = 0, len(nums)
        while left < right:
            mid = left + right >> 1
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

    """
    给定一个整数数组，判断是否存在重复元素。

    如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。"""

    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        s = set()
        s.clear()
        for num in nums:
            if num not in s:
                s.add(num)
            else:
                return True
        return False

    """
    给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
    
    任何数和自己做异或运算，结果为 0，即 a⊕a=0a⊕a=0 。
    任何数和 0 做异或运算，结果还是自己，即 a⊕0=⊕a⊕0=⊕。
    异或运算中，满足交换律和结合律，也就是 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=ba⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
    """

    def add(self, x, y):
        return x + y

    def singleNumber(self, nums: List[int]) -> int:
        sum2 = reduce(lambda x, y: x + y, [1, 2, 3, 4, 5])
        print(reduce(lambda x, y: x ^ y, nums))
        print(reduce(self.add, [1, 2, 3]))
        print(sum2)
        return reduce(lambda x, y: x ^ y, nums)

    def popp(self, lst):
        for i in range(len(lst)):
            if lst[i] == 1:
                print(lst.pop(i))
                lst.insert(0, lst.pop(i))

        print("处理后的数组为: ", lst)

    # def rev_str(self):
    #     str1 = "hello,how are you?"

    def count0(self):
        for i in range(1, 1001):
            result = i * i

    def containsDuplicatee(self, numss: List[int]) -> bool:
        return len(set(nums)) != len(nums)

    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        former, latter = head, head
        for _ in range(k):
            former = former.next
        while former:
            former, latter = former.next, latter.next
        return latter

    def findRepeatNumber1(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        num = []
        for i in nums:
            if i in num:
                print(i)
                return i
            else:
                num.append(i)

    # 删除有序数组中重复数
    def removeDuplicates1(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        if not nums:
            return 0

        n = len(nums)
        fast = slow = 1
        while fast < n:
            if nums[fast] != nums[fast - 1]:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1

        return slow

    # 查找数组中出现次数大于数组长度一半的元素
    # def majorityElement(self, nums: List[int]) -> int:
    #     counts = collections.Counter(nums)
    #     print(max(counts.keys(), key=counts.get))
    #     print(counts.keys())
    #     print(counts)
    #     key = counts.get
    #     print(key)
    #     return max(counts.keys(), key=counts.get)
    # Counter获取各元素的个数，返回字典
    # 查找数组中出现次数大于数组长度一半的元素.次数多的是众数
    def majorityElement(self, nums):
        counts = collections.Counter(nums)
        return max(counts.keys())

    def majorityElement1(self, nums):
        nums.sort()
        print(len(nums))
        return nums[len(nums) // 2]

    def majorityElement1(self, nums: List[int]) -> int:
        votes = 0
        for num in nums:
            if votes == 0: x = num
            votes += 1 if num == x else -1
        print(x)
        return x



    # 合并两个有序数组
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # i缺省时默认为0, 即
        # a[:n]
        # 代表列表中的第一项到第n项，相当于
        # a[0:n]
        nums1[m:] = nums2
        print(nums1)
        nums1.sort()
        print(nums1)

    def findLen(self, str):
        counter = 0
        while str[counter:]:
            counter += 1
            print(counter)
        return counter

    # 给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        x = s.split(" ")
        str_x = x[::-1]
        print(str_x)
        for i in str_x:
            if len(i) != 0:
                print(len(i))
                return i
            # else:
            #     i = i + 1


class Stack:
    # 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
    def __init__(self):
        self.stackA, self.stackB = [], []

    def appendTail(self, value):
        """
        :type value: int
        :rtype: None
        """
        self.stackA.append(value)

    def deleteHead(self):
        """
        :rtype: int
        """
        if self.stackB:
            return self.stackB.pop()
        if not self.stackA:
            return -1
        while self.stackA:
            self.stackB.append(self.stackA.pop())

        return self.stackB.pop()


if __name__ == '__main__':
    # nums = [1, 0, 1, 1, 1]
    # target = 8
    s = Solution()
    # # s.twoSum(numbers=nums, target=target)
    # # s.db()
    list1 = [1, 2, 3, 4]
    list2 = [1, 4, 3, 6]
    # # s.mergeTwoLists(l1=list1, l2=list2)
    # # s.popp(nums)
    # # s.majorityElement(nums=nums)
    # str = 'fdafdaf reb req rqr4  '
    # # s.findLen(str=str)
    s.merge(nums1=list1, nums2=list2, m=4, n=4)
    # s.lengthOfLastWord(s=str)
    st = Stack()
